package everyday;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author zhangmin
 * @create 2022-05-03 10:11
 * 除法求值
 * 给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
 * 另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
 * 返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
 *
 * 思路：并查集
 * 将除数和被除数的表达式都抽象成并查集中的节点，然后依据除法关系构建联通关系
 */
public class calcEquation399 {
    public class UF{
        private int[] parent;
        private double[] weight;
        public UF(int n){
            this.parent=new int[n];
            this.weight=new double[n];
            for (int i = 0; i < n; i++) {
                //初始状态每个节点都是不连通的
                parent[i]=i;
                weight[i]=1.0d;
            }
        }
        //找到x的根节点,顺便进行路径压缩，将每个节点都和根节点连接
        public int find(int x){
            if (parent[x]!=x){
                int cur=parent[x];
                //递归去压缩上面的路径
                parent[x]=find(parent[x]);
                //当前节点的权重和它父亲的权重有关，因为如果cur的权重为3，表示cur和它的父亲节点（假设是a），则cur/a=3,x的权重表示x/cur=2,则将x接到a表示x/a=（x/cur）*（cur/a)=2*3
                weight[x]*=weight[cur];
            }
            return parent[x];
        }

        //将p，q联通，将p指向q，pq之间权重为value
        public void union(int p,int q,double value){
            int rootp = find(p);
            int rootq = find(q);
            if (rootp==rootq) return;
            parent[rootp]=rootq;
            weight[rootp]=weight[q]*value/weight[p];
        }
        //判断pq是否联通
        public double isConnect(int p,int q){
            int rootp = find(p);
            int rootq = find(q);
            if (rootp==rootq){
                return weight[p]/weight[q];
            }else {
                return -1.0d;
            }
        }
    }

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int n=equations.size();
        UF uf=new UF(2*n);
        //记录一下变量和并查集中的节点的对应关系
        Map<String,Integer> map=new HashMap<>();
        int id=0;
        for (int i = 0; i < n; i++) {
            List<String> equation = equations.get(i);
            String cur1 = equation.get(0);
            String cur2 = equation.get(1);
            if (!map.containsKey(cur1)){
                map.put(cur1,id++);
            }
            if (!map.containsKey(cur2)){
                map.put(cur2,id++);
            }
            uf.union(map.get(cur1),map.get(cur2),values[i]);
        }
        //计算结果
        int nn=queries.size();
        double[] res=new double[nn];
        for (int i = 0; i < nn; i++) {
            Integer id1 = map.get(queries.get(i).get(0));
            Integer id2 = map.get(queries.get(i).get(1));
            if (id1==null||id2==null){
                res[i]=-1.0d;
            }else {
                res[i]=uf.isConnect(id1,id2);
            }
        }
        return  res;
    }
}
